! git log -1 --format="%H"
28688145c190ebc1427f3830d5580e6337c2ebbf
import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 1
# The number of cities in the core net
NC = 4
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 1
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 9389, C = 6153
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
2460 | is_connectable
123 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
164 | is_connected_step
5043 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 1200.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 1200.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6153 rows, 9389 columns and 30299 nonzeros
Model fingerprint: 0x62542997
Model has 4 SOS constraints
Model has 820 general constraints
Variable types: 2460 continuous, 6929 integer (6929 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [8e-01, 4e+01]
Presolve removed 90 rows and 2633 columns
Presolve time: 0.10s
Presolved: 6063 rows, 6756 columns, 30429 nonzeros
Variable types: 2460 continuous, 4296 integer (4296 binary)
Found heuristic solution: objective 90385.781789
Root relaxation: objective 1.509308e+03, 5423 iterations, 0.15 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1509.30849 0 156 90385.7818 1509.30849 98.3% - 0s
H 0 0 89740.648793 1997.31513 97.8% - 0s
0 0 2968.88325 0 258 89740.6488 2968.88325 96.7% - 0s
H 0 0 67997.987041 2968.88325 95.6% - 0s
0 0 2969.67773 0 213 67997.9870 2969.67773 95.6% - 0s
0 0 2970.42479 0 210 67997.9870 2970.42479 95.6% - 0s
0 0 2970.43911 0 213 67997.9870 2970.43911 95.6% - 0s
0 0 3237.87671 0 330 67997.9870 3237.87671 95.2% - 1s
H 0 0 48797.457839 3237.87671 93.4% - 1s
0 0 3245.19390 0 320 48797.4578 3245.19390 93.3% - 1s
0 0 3247.99716 0 326 48797.4578 3247.99716 93.3% - 1s
0 0 3248.18066 0 326 48797.4578 3248.18066 93.3% - 1s
0 0 3259.02907 0 266 48797.4578 3259.02907 93.3% - 1s
0 0 3268.25931 0 267 48797.4578 3268.25931 93.3% - 1s
0 0 3269.30478 0 268 48797.4578 3269.30478 93.3% - 1s
0 0 3281.06354 0 354 48797.4578 3281.06354 93.3% - 1s
0 0 3285.17645 0 357 48797.4578 3285.17645 93.3% - 1s
0 0 3285.96567 0 398 48797.4578 3285.96567 93.3% - 1s
H 0 0 44938.270900 3285.96567 92.7% - 1s
0 0 3285.96567 0 362 44938.2709 3285.96567 92.7% - 1s
0 0 3286.14392 0 379 44938.2709 3286.14392 92.7% - 1s
H 0 0 23831.342637 3286.14392 86.2% - 1s
0 0 3286.14392 0 271 23831.3426 3286.14392 86.2% - 2s
H 0 0 23512.577517 3286.14392 86.0% - 2s
H 0 0 17596.640729 3286.14392 81.3% - 2s
H 0 2 17530.853373 3286.20130 81.3% - 2s
0 2 3286.20130 0 249 17530.8534 3286.20130 81.3% - 2s
H 31 40 17509.553165 3651.30955 79.1% 553 3s
H 32 40 17403.867361 3653.44769 79.0% 563 3s
H 35 40 17390.153268 3653.44769 79.0% 530 3s
H 36 40 17357.273390 3653.44769 79.0% 520 3s
H 38 40 17347.093730 3653.44769 78.9% 516 3s
H 64 76 17201.676278 3654.31036 78.8% 393 3s
H 70 76 17160.478861 3654.31036 78.7% 396 3s
H 104 112 15172.939366 3654.31036 75.9% 323 3s
H 155 145 15137.749975 3654.31036 75.9% 246 4s
H 156 145 15087.253910 3654.31036 75.8% 245 4s
H 260 259 15073.424965 3654.31036 75.8% 175 4s
H 264 259 15026.845333 3654.31036 75.7% 172 4s
H 277 259 15013.016387 3654.31036 75.7% 168 4s
* 533 487 38 14412.907210 3654.31036 74.6% 126 4s
555 528 5258.94136 92 207 14412.9072 3654.31036 74.6% 123 5s
H 1229 967 14412.907201 3838.77445 73.4% 128 7s
1483 1131 11689.5787 42 271 14412.9072 4050.83986 71.9% 131 11s
1499 1142 11168.5795 19 262 14412.9072 4050.83986 71.9% 130 15s
1504 1149 4050.83986 15 251 14412.9072 4050.83986 71.9% 146 21s
1547 1167 8770.08434 19 250 14412.9072 4050.83986 71.9% 157 25s
1766 1202 6874.14300 26 188 14412.9072 4050.83986 71.9% 169 30s
2451 1286 5283.79397 25 213 14412.9072 4050.83986 71.9% 173 35s
H 2800 1307 14389.985397 4050.83986 71.8% 176 37s
H 2889 1310 14387.970618 4050.83986 71.8% 177 38s
H 2894 1258 14387.425093 4050.83986 71.8% 178 38s
H 2902 1205 14385.410314 4050.83986 71.8% 178 38s
3299 1357 6086.81226 32 193 14385.4103 4137.79699 71.2% 176 40s
H 3659 1338 14381.924357 4651.41659 67.7% 176 43s
3835 1425 6553.85045 31 247 14381.9244 4753.62910 66.9% 175 45s
4707 1768 6877.64793 23 174 14381.9244 5747.99224 60.0% 177 50s
H 4924 1873 13948.648888 5896.65043 57.7% 175 51s
H 5138 1889 13947.833817 6004.85635 56.9% 175 52s
H 5202 1889 13947.833807 6047.83848 56.6% 175 52s
5781 2072 cutoff 39 13947.8338 6249.06593 55.2% 174 55s
H 6762 2376 13947.833787 6491.65701 53.5% 173 59s
H 6854 2458 13947.833755 6526.76860 53.2% 173 61s
H 6881 2458 13947.833706 6532.09523 53.2% 173 61s
7723 2881 7964.33521 34 203 13947.8337 6761.53808 51.5% 171 65s
H 8438 3143 13947.833701 6886.57939 50.6% 170 68s
H 8621 3143 13947.833682 6910.04879 50.5% 168 68s
9225 3484 13640.7436 40 125 13947.8337 7051.45124 49.4% 167 71s
H 9756 3635 13947.833645 7129.23778 48.9% 166 72s
H10009 3635 13947.833632 7159.15754 48.7% 166 72s
10536 4041 9377.81059 34 147 13947.8336 7280.52156 47.8% 166 76s
H11118 4315 13947.833582 7327.42059 47.5% 164 79s
11619 4549 8294.77877 33 162 13947.8336 7425.52051 46.8% 164 81s
13087 5061 9497.48408 35 164 13947.8336 7660.13929 45.1% 163 86s
14451 5435 8058.78403 26 196 13947.8336 7817.35138 44.0% 162 91s
15816 5707 cutoff 62 13947.8336 8021.43734 42.5% 162 96s
17066 6101 infeasible 40 13947.8336 8223.26495 41.0% 162 100s
19362 6636 cutoff 41 13947.8336 8467.52890 39.3% 161 106s
21016 6946 13139.0928 43 93 13947.8336 8659.33824 37.9% 161 111s
22821 7198 11726.8466 52 87 13947.8336 8843.13370 36.6% 160 115s
24208 7386 11034.2509 48 106 13947.8336 8995.61081 35.5% 160 120s
H25243 7364 13947.833563 9125.13107 34.6% 160 123s
25323 7377 9487.09427 38 142 13947.8336 9150.06006 34.4% 160 126s
26970 7374 cutoff 32 13947.8336 9376.40545 32.8% 160 131s
28276 7327 13414.1662 35 150 13947.8336 9502.01081 31.9% 160 136s
29680 7206 cutoff 45 13947.8336 9673.73902 30.6% 160 141s
30445 7121 13394.1440 22 193 13947.8336 9770.65267 29.9% 160 152s
31146 7032 13825.7599 38 83 13947.8336 9843.18798 29.4% 160 155s
33334 6703 cutoff 37 13947.8336 10159.5969 27.2% 159 160s
36344 5713 12993.5971 30 164 13947.8336 10539.2061 24.4% 158 167s
38467 4880 11403.2213 36 145 13947.8336 10989.1327 21.2% 157 171s
39824 4298 12745.2994 41 104 13947.8336 11200.1618 19.7% 156 176s
42283 3037 cutoff 42 13947.8336 11586.5342 16.9% 154 180s
45778 653 13145.8432 48 85 13947.8336 12289.9975 11.9% 149 185s
Cutting planes:
Gomory: 49
Cover: 379
Implied bound: 16
Clique: 1
MIR: 112
Flow cover: 258
GUB cover: 14
Inf proof: 13
Zero half: 43
RLT: 239
Relax-and-lift: 18
Explored 51954 nodes (6965443 simplex iterations) in 188.66 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 13947.8 13947.8 13947.8 ... 14385.4
Optimal solution found (tolerance 1.00e-04)
Best objective 1.394783356342e+04, best bound 1.394783356342e+04, gap 0.0000%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 4.4 | 2.699999e+00 | 7.100000 |
| 1 | 1 | Borås | False | False | 3.4 | 2.100000e+01 | 24.400000 |
| 2 | 2 | Eskilstuna | False | False | 3.2 | 6.200000e+00 | 9.400000 |
| 3 | 3 | Falun | False | False | 4.6 | 3.357314e-13 | 4.600000 |
| 4 | 4 | Gävle | False | False | 2.6 | 2.380000e+01 | 26.400000 |
| 5 | 5 | Göteborg | False | False | 6.4 | 1.350031e-13 | 6.400000 |
| 6 | 6 | Halmstad | False | False | 4.0 | 7.400000e+00 | 11.400000 |
| 7 | 7 | Haparanda | False | False | 1.1 | 0.000000e+00 | 1.100000 |
| 8 | 8 | Helsingborg | False | False | 3.0 | 4.400000e+00 | 7.400000 |
| 9 | 9 | Hudiksvall | False | False | 1.5 | 1.880000e+01 | 20.300000 |
| 10 | 10 | Jönköping | True | False | 2.2 | 1.106000e+02 | 112.799999 |
| 11 | 11 | Kalmar | False | False | 1.9 | 7.958079e-13 | 1.900000 |
| 12 | 12 | Karlskrona | False | False | 3.2 | 3.836931e-13 | 3.200000 |
| 13 | 13 | Karlstad | False | False | 4.4 | 1.230127e-12 | 4.400000 |
| 14 | 14 | Kiruna | False | False | 2.7 | 1.563194e-13 | 2.700000 |
| 15 | 15 | Kristianstad | False | False | 3.9 | 4.121148e-13 | 3.900000 |
| 16 | 16 | Lidköping | False | False | 3.4 | 2.700000e+00 | 6.100000 |
| 17 | 17 | Linköping | True | False | 4.6 | 1.161000e+02 | 120.699999 |
| 18 | 18 | Luleå | False | False | 0.9 | 8.200000e+00 | 9.100000 |
| 19 | 19 | Malmö | False | False | 0.8 | 3.600000e+00 | 4.400000 |
| 20 | 20 | Motala | True | False | 3.6 | 6.020000e+01 | 63.800000 |
| 21 | 21 | Norrköping | True | True | 3.9 | 1.704000e+02 | 53.599999 |
| 22 | 22 | Nyköping | False | False | 1.7 | 3.860000e+01 | 40.300000 |
| 23 | 23 | Sandviken | False | False | 3.5 | 1.385558e-12 | 3.500000 |
| 24 | 24 | Skellefteå | False | False | 1.8 | 9.100000e+00 | 10.900000 |
| 25 | 25 | Skövde | False | False | 1.0 | 6.100000e+00 | 7.100000 |
| 26 | 26 | Stockholm | False | False | 9.2 | 2.940000e+01 | 38.600000 |
| 27 | 27 | Sundsvall | False | False | 1.0 | 1.780000e+01 | 18.800000 |
| 28 | 28 | Trelleborg | False | False | 3.6 | 1.140421e-12 | 3.600000 |
| 29 | 29 | Uddevalla | False | False | 1.2 | 1.968203e-12 | 1.200000 |
| 30 | 30 | Umeå | False | False | 2.4 | 1.090000e+01 | 13.300000 |
| 31 | 31 | Uppsala | False | False | 3.0 | 2.640000e+01 | 29.400000 |
| 32 | 32 | Varberg | False | False | 3.2 | 1.140000e+01 | 14.600000 |
| 33 | 33 | Vetlanda | False | False | 2.8 | 1.250000e+01 | 15.299999 |
| 34 | 34 | Vänersborg | False | False | 1.5 | 1.200000e+00 | 2.700000 |
| 35 | 35 | Västervik | False | False | 3.3 | 2.692957e-12 | 3.300000 |
| 36 | 36 | Västerås | False | False | 1.6 | 4.600000e+00 | 6.200000 |
| 37 | 37 | Växjö | False | False | 3.5 | 7.100000e+00 | 10.599999 |
| 38 | 38 | Örebro | False | False | 2.2 | 4.400000e+00 | 6.600000 |
| 39 | 39 | Örnsköldsvik | False | False | 2.2 | 1.330000e+01 | 15.500001 |
| 40 | 40 | Östersund | False | False | 2.3 | 1.197265e-12 | 2.300000 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 10.900000 | 413.098300 | 111 |
| 1 | Eskilstuna | Västerås | SUB | -6.200000 | 65.283353 | 43 |
| 2 | Gävle | Hudiksvall | SUB | -20.300000 | 832.846922 | 118 |
| 3 | Norrköping | Nyköping | SUB | -40.300000 | 572.920463 | 58 |
| 4 | Nyköping | Stockholm | SUB | -38.600000 | 1052.200000 | 90 |
| 5 | Linköping | Norrköping | CORE | 120.699999 | 440.000000 | 44 |
| 6 | Karlskrona | Växjö | SUB | 3.200000 | 114.243800 | 102 |
| 7 | Motala | Örebro | SUB | -6.600000 | 194.172879 | 92 |
| 8 | Boden | Kiruna | SUB | -2.699999 | 433.841113 | 291 |
| 9 | Sundsvall | Östersund | SUB | -2.300000 | 165.557112 | 166 |
| 10 | Halmstad | Helsingborg | SUB | -7.400000 | 174.313163 | 79 |
| 11 | Jönköping | Vetlanda | SUB | -15.299999 | 263.548737 | 65 |
| 12 | Umeå | Örnsköldsvik | SUB | 13.300000 | 501.853888 | 111 |
| 13 | Lidköping | Skövde | SUB | 6.100000 | 76.164335 | 49 |
| 14 | Karlstad | Örebro | SUB | 4.400000 | 104.013185 | 77 |
| 15 | Halmstad | Varberg | SUB | 11.400000 | 198.918673 | 65 |
| 16 | Lidköping | Vänersborg | SUB | -2.700000 | 49.681734 | 60 |
| 17 | Uddevalla | Vänersborg | SUB | 1.200000 | 13.651827 | 21 |
| 18 | Gävle | Sandviken | SUB | -3.500000 | 23.834965 | 25 |
| 19 | Hudiksvall | Sundsvall | SUB | -18.800000 | 443.396478 | 81 |
| 20 | Borås | Göteborg | SUB | -6.400000 | 131.078630 | 71 |
| 21 | Falun | Västerås | SUB | 4.600000 | 220.655469 | 128 |
| 22 | Jönköping | Linköping | CORE | 112.799999 | 1250.000000 | 125 |
| 23 | Linköping | Västervik | SUB | -3.300000 | 109.694578 | 97 |
| 24 | Sundsvall | Örnsköldsvik | SUB | -15.500001 | 711.515537 | 127 |
| 25 | Jönköping | Motala | CORE | -63.800000 | 1080.000000 | 108 |
| 26 | Vetlanda | Växjö | SUB | -10.599999 | 214.788040 | 72 |
| 27 | Borås | Varberg | SUB | -14.600000 | 365.444489 | 84 |
| 28 | Haparanda | Luleå | SUB | 1.100000 | 58.031396 | 124 |
| 29 | Luleå | Skellefteå | SUB | 9.100000 | 451.386305 | 133 |
| 30 | Stockholm | Uppsala | SUB | -29.400000 | 542.869627 | 69 |
| 31 | Motala | Norrköping | CORE | -53.599999 | 790.000000 | 79 |
| 32 | Kristianstad | Växjö | SUB | 3.900000 | 172.119956 | 120 |
| 33 | Gävle | Uppsala | SUB | 26.400000 | 397.999175 | 60 |
| 34 | Helsingborg | Malmö | SUB | -4.400000 | 74.666529 | 60 |
| 35 | Borås | Jönköping | SUB | 24.400000 | 582.941928 | 82 |
| 36 | Jönköping | Skövde | SUB | -7.100000 | 173.676329 | 81 |
| 37 | Boden | Luleå | SUB | 7.100000 | 50.642772 | 32 |
| 38 | Malmö | Trelleborg | SUB | -3.600000 | 32.569445 | 34 |
| 39 | Eskilstuna | Norrköping | SUB | 9.400000 | 316.216147 | 102 |
| 40 | Kalmar | Vetlanda | SUB | 1.900000 | 87.996287 | 119 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 3560.000 subnet = 10387.834 ------------------ total = 13947.834
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))